public class Code {
    // 买卖股票问题 IV (买卖股票的终极问题)

    public int maxProfit(int k, int[] prices) {
        // 对于这个问题，使用动态规划来解决与前一个 买卖股票的最佳时机III 解法非常相似，这里就不进行过多的描述

        // 由题目可知，这里买卖的最大次数为 k 次
        // 首先，我们可以先针对这个问题进行一下优化操作
        // 假设 k=30 但是这里的股票交易只有 20 天，即只能进行 20/2 = 10 次。可以有下面的优化操作
        int n = prices.length;
        k = Math.min(k, n/2);

        // 创建 dp 表
        // 这里有两个状态，对此这需要有两 参数 的表来存储利润信息
        // f “买入”  g “卖出”
        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];

        // 实现初始化操作
        // 将两个表中第一行除了第一个位置的数据，其余位置设置为 -0x3f3f3f3f
        int INF = -0x3f3f3f3f;
        for(int j = 0; j <= k; j++){
            f[0][j] = g[0][j] = INF;
        }
        // 在针对第一个位置进行初始化
        f[0][0] = -prices[0];
        g[0][0] = 0;

        // 进行填表操作，从左往右、从上到下
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= k; j++){
                // 针对 当天结束后为 “买入” 状态下的填写
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                // 针对 当天结束后为 “卖出” 状态下的填写
                // 这里需要对 j 即交易次数列要进行控制
                g[i][j] = g[i - 1][j];
                if(j >= 1)
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        // 确定返回值
        int ret = 0;
        // 这里只需要考虑手中没有股票时的 g 表即可
        for(int i = 0; i <= k; i++){
            ret = Math.max(ret, g[n - 1][i]);
        }
        return ret;
    }
}
